package l.l.w.CodingInterviews;

import java.util.Stack;

/**
 * Created by llw on 2018/4/13/0013.
 */
public class 二叉搜索树的第k个结点 {
    TreeNode KthNode1(TreeNode pRoot, int k){
        int[] i = new int[1];
        return inOrder(pRoot, k, i);
    }
    TreeNode KthNode(TreeNode root, int k){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode p = root;
        int i = 0;
        while (!stack.isEmpty() || p != null){
            if(p != null){
                stack.push(p);
                p = p.left;
            }else{
                TreeNode node = stack.pop();
                i++;
                if(i == k) return node;
                p = node.right;

            }
        }
        return null;
    }
    private TreeNode inOrder(TreeNode root, int k, int[] i){
        if(root == null) return null;
        TreeNode result = inOrder(root.left, k, i);
        if(result != null) return result;
        i[0] = i[0] + 1;
        if(i[0] == k) return root;
        result = inOrder(root.right, k, i);
        return result;
    }
}
